/*
 * @lc app=leetcode.cn id=34 lang=typescript
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start

//  思路：二分查找
//  根据中间数和target的大小关系来缩短判断范围
//  找到相等的数后再向外扩展比较

//  复杂度：O(logn) O(1)

function searchRange(nums: number[], target: number): number[] {
    let res = [-1, -1]
    let left = 0, right = nums.length - 1
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2)
        if (nums[mid] < target) {
            left = mid + 1
        } else if (nums[mid] > target) {
            right = mid - 1
        } else {
            left = mid
            right = mid
        }
    }
    while (nums[left] === target) {
        res[0] = left
        left--
    }
    while (nums[right] === target) {
        res[1] = right
        right++
    }
    return res
};
// @lc code=end

console.log(searchRange([5, 7, 7, 8, 8, 10], 8))  // [3,4]
console.log(searchRange([5, 7, 7, 8, 8, 10], 6))  // [-1,-1]
console.log(searchRange([], 0))                   // [-1,-1]
